Subgroups and Cosets

Throughout this section let G denote a group, H G a nonempty subset. Our goal is to study the properties of those subsets H which are groups.

Definition 1: We say that H is a subgroup of G if H is a group with respect to the multiplication · of G.

Since · is already associative with respect to the elements of G, it is automatically associative for elements of H. Therefore, from the group axioms, we deduce that H is a subgroup of G if and only if H has the following properties

SG1: H is closed under · ; that is, for x,y H, we have x · y H.

SG2: 1_G H.

SG3: If x H, then x^-1 H.

These three properties can be combined into a simple test for H to be a subgroup:

Proposition 2: Let H G, H . Then H is a subgroup if and only if for a,b H, we have a · b^-1 H.

Proof: There are two statements to prove. First assume that H is a subgroup of G and that a,b H Let us show that a · b^-1 H. By (SG3), b^-1 H, and therefore by (SG1), a · b^-1 H.

Conversely, assume that H G and that for a,b H, we have a · b^-1 H. It suffices to show that the properties (SG1)-(SG3) are satisfied. Since H , there exists a H. Therefore, 1_G = a · a^-1 H and thus (SG2) holds. Moreover, if b H, b^-1 = 1_G· b^-1 H. Therefore, (SG3) holds. Finally, if a,b H, then b^-1 H. by (SG3), which we have just proved. Note that (b^-1)^-1 = b since b^-1· b = b · b^-1 = 1_G. Therefore, a · b = a·(b^-1)^-1 H and (SG1) holds.

Example 1: Let G denote the group of symmetries of the square. Two subgroups of G are given by

Example 2: More generally, the dihedral group D_n contains two subgroups.

Example 3: Let k Z, and let

kZ = {k · r | r Z}.

Then kZ is a subgroup of Z, considered as a group under addition.

Example 4: The group C of continuous functions on R is a subgroup of the group of all functions on R.

Example 5: Let f be the polynomial (x²- 2)(x²- 3) with roots +, +. The set of permutations of the roots forms a group (essentially S₄). The four permutations of this group defined by +, -+, +, and -+ form a subgroup.

If is any nonempty collection of subgroups of the group G, then the intersection H^* = is a subgroup of G.

Theorem 3: If is any nonempty collection of subgroups of the group G, then the intersection

H^* =

is a subgroup of G.

Proof: First observe that H^* since 1_G H for all H , so that 1_G H^*. Let us apply Proposition 2. Let a,b H^*. Then, for every H , we have a,b H. Thus, since H is a subgroup of G, a·b^-1 H. Therefore, a·b^-1 H^* and H^* is a subgroup of G.

We shall now consider a general technique for manufacturing subgroups of a group G. Let S be any subset of G. Let be the collection of all subgroups containing S. is nonempty because G . By Theorem 3

[S] =

is a subgroup of G and by the definition of , [S] contains S. Actually [S] is the smallest subgroup of G which contains S. For if H is a subgroup of G containing S, then H , so that [S] H.

Definition 4: [S] is called the subgroup of G generated by S. If [S] = G, then S is said to be a set of generators for G.

We can give another description of [S]. It is clear that [S] contains all products of the form

where either a_i S or a_i^-1 S (1 < i < n). But the set of all these products forms a subgroup H of G. And this subgroup contains S. Therefore [S] H. But we also have H [S]. Therefore, H = [S]. In other words, [S] is the subgroup of G consisting of all products of the form (1). For example, D_n is generated by S = {R, F}.

Definition 5: A group G is said to be cyclic if G is generated by a single element. That is, G is cyclic if there exists a G such that G = [S], where S = {a}.

From our above characterization of [S] we see that G is cyclic if and only if there exists a G such that

The element a is usually not unique. Moreover, the various powers of a need not all be distinct. We will study this possibility more closely below.

Cyclic groups are the simplest groups. Later we will prove the fundamental theorem of abelian groups, which states that the cyclic groups are the building blocks from which abelian groups with a finite number of generators can be built.

We have already met several examples of cyclic groups.

Example 6: G = Z is a cyclic group. As a generator we may take 1.

Example 7: G = Z_n(residue classes modulo n) is a finite cyclic group of order n. As a generator we may take 1.

Example 8: Let G be an arbitrary group, a G. Set S = {a}. Then [S] is a cyclic subgroup of G. We will usually denote this subgroup by [a].

Definition 6: Let G be a group and let a G. If [a] is finite, then we define the order of a to be the number of elements in [a]. If [a] is infinite, we define the order of a to be infinity.

Proposition 7: Suppose that a has finite order r. Then r is the smallest positive integer such that a^r = 1_G, and [a] = {1_G,a,...,a^r-1}.

Proof: Since [a] is finite, not all of the powers a^m (m N) are distinct. Suppose that a^m = aⁿ (m, n > 0, m > n). Then a^m-n = 1_G and m - n > 0. Therefore, there exist positive integers r such that a^r = 1_G. Let r be the smallest such. We will prove that [a] = {1_G=a⁰, a, a²,...,a^r-1}, where the powers of a mentioned are all distinct. Indeed, if aⁱ = a^j (0 < i < j < r-1), then a^j-i = 1_G and 0 < j-i < r, which is a contradiction to the definition of r. Therefore, the powers a^j (0 < j < r-1) are all distinct. Let [a]. In order to prove our assertion, it suffices to show that = a^j for some j (0 < j < r-1). But = aⁿ for some n Z. Assume for the moment that n > 0. By the division algorithm, there exist p,q N such that

n = pr + q    (0 < q < r - 1).

Then

= aⁿ = a^pr+q = (a^r)^pa^q

= a^q    (since a^r = 1).

Thus, we are done in the case n > 0. If n < 0, then -n > 0, so that by what we have already proved, we see that ^-1 = a^-n = a^j for some j (0 < j < r - 1). If j = 0, then we may take n = 0, in which case the assertion has already been proved. Thus we may assume that j > 0. Then

= a^-j = a^ra^-j = a^r-j

and 0 < r - j < r - 1. Thus, the assertion is proved for n < 0.

Proposition 8: Suppose that a has infinite order. Then a^r 1_G for all r Z-{0}, and [a] = {...,a^-2,a^-1,1_G,a,a²,...}, where all the powers of a are distinct.

Proof: It suffices to consider the case r > 0, for if a^r = 1_G, then a^-r = 1_G. By exactly the same reasoning as we used to prove Proposition 7, we see that if, for some r > 0, we have a^r = 1_G, then

(The powers of a may not all be distinct, however.) But this contradicts the fact that [a] is infinite. Moreover, if aⁱ = a^j, then a^i-j= 1_G, so that i - j = 0 by what we just proved. Thus, all powers of a are distinct.

Combining Propositions 7 and 8 we can say something about cyclic groups. Let G be a cyclic group with generator a. There are two cases to consider

Case 1: G is finite. Suppose that G has order r. Then by Proposition 7,

and a^r = 1_G.

Case 2: G is infinite. In this case,

where all powers of a are distinct.

Note that in case 1, G closely resembles Z_r, while in case 2, G closely resembles Z. In fact, in a later section, we will show that for purposes of group theory, any cyclic group is either Z of Z_r.

Let us now return to the consideration of the subgroups of an arbitrary group G. One very important, but difficult, problem is to determine all of the subgroups of G. When G is finite, the problem can be solved by brute force. For we can list all of the subsets of G and then test each subset to determine whether it is a subgroup. But this solution to the problem is not very practical. Therefore, we must look for some simple criteria which can rule out most subsets of G from being subgroups. The simplest criterion is due to Lagrange and is one of the most fundamental theorems in the theory of groups.

Theorem 9(Lagrange): Let G be a finite group, H a subgroup of G. Then the order of H divides the order of G.

Before proving Lagrange's theorem, it will be necessary for us to build up some machinery. This machinery may seem very ad hoc at this time, but the ideas we will develop here will be quite natural and will be extremely important later when we define quotient groups

Let a G and set

Ha = {ha | h H},

The set Ha is called a right coset of G with respect to H. We could just as easily consider left cosets of the form

aH = {ah | h H}.

But throughout this argument, we will stick to right cosets. We will denote the set of all right cosets of G with respect to H by H\G. The set of all left cosets will be denoted G/H. The element a is called a representative of aH.

Lemma 10: All right cosets contain |H| elements.

Proof: It is clear that Ha contains at most |H| elements. In order to prove that the number is exactly |H|, it suffices to show that all the elements h · a (h H) are different. But if

h₁·a = h₂·a    (h₁, h₂ H),

we have h₁= h₂ on multiplying on the right by a^-1.

Lemma 11: If Ha Hb , then Ha = Hb.

Proof: Let g Ha Hb. Then

g = h₁· a = h₂· b   (h₁,h₂ H)

Therefore, a = h₁^-1· h₂· b and

Since H is a subgroup, h₁^-1· h₂ H, so that Hh₁^-1·h₂ H. Moreover, if h H, then h = (h · h₂^-1· h₁) · (h₁^-1· h₂) Hh₁^-1· h₂. Therefore, H Hh₁^-1· h₂ and we have shown that H = Hh₁^-1· h₂. Thus, by (1),

Every element of G is contained in some right coset. For example, a is contained in Ha. Let the number of distinct cosets of G with respect to H be k. Then if the right cosets are

we can write

G = Ha₁ Ha₂ ... Ha_k.

By Lemma 11, the union of (2) defines a partition of G and, by Lemma 10, each subset of the partition contains |H| elements.

Proof of Lagrange's Theorem: Let |G| = n, |H| = m. Then by (2) and the remarks just made, we see that

n = km |H||G|.

Earlier we showed that with every partition of a set, there is associated an equivalence relation such that the subsets in the partition are precisely the equivalence classes of the equivalence relation. In the case of the partition (2), the equivalence relation is

a ~ b b · a^-1 H.

Remark: Lagrange's theorem does not assert that if m is a positive integer which divides the order of G, then there exists a subgroup H of G having order m. In fact, this statement is false.

Lagrange's theorem has a number of very important consequences. To mention but a few:

Corollary 12: Let G be a finite group, a G. Then the order of a divides |G|.

Proof: The order of a equals the order of the subgroup [a] of G. Therefore, the assertion follows directly from Lagarange's theorem.

Corollary 13: Let G be a finite group of order n, a G. Then aⁿ = 1_G.

Proof: Let m denote the order of a. Then by Corollary 12, m|n n = m · k for some positive integer k. Therefore,

aⁿ = a^mk = (a^m)^k = 1_G^k = 1_G.

Corollary 14: A group of prime order is cyclic.

Proof: Let G have a prime order p. Then the only positive divisors of p are 1 and p. Let a G, a 1_G. By Corollary 12, the order of [a] divides p, so that [a] has either 1 or p elements. But [a] contains 1_G and a, so that [a] has p elements. Therefore, G = [a] and G is cyclic.

Corollary 15: Let n be a positive integer, (a,n) = 1. Then

a⁽ⁿ⁾1 (mod p).

where (n) denotes Euler's function. In particular, if p is prime and p a, then

a^p-1 1 (mod p).

Proof: Let us apply Corollary 13 to the element a of the group Z_n^x of order (n). We get that

a⁽ⁿ⁾ = a⁽ⁿ⁾ = 1.

Therefore,

a⁽ⁿ⁾ 1 (mod n).

Corollary 15 was first discovered by Pierre Fermat in case n = a prime number and is known as "Fermat's little theorem." The general form of Corollary 15 is due to Euler.

Let m be a positive integer. Since [a^m] is a subgroup of [a], Corollary 12 implies that the order of a^m divides the order of a. However, we can be much more specific:

Theorem 16: Let a have order n. then a^m has order n/(n,m). In particular if (m,n) = 1, then a^m has order n.

Proof: Let us first consider two special cases of the theorem:

Case 1: m|n. Suppose that n = k · m. Then (n,m) = m, so that we must prove that a^m has order n/m = k. First, it is clear that (a^m)^k = aⁿ = 1_G. Suppose that r is a positive integer less than k such that (a^m)^r = 1_G. Then a^mr = 1_G and m · r < n. But this contradicts the assumption that n is the smallest positive integer such that aⁿ = 1_G. Thus, k is the smallest positive integer such that (a^m)^k = 1_G; that is a^m has order k.

Case 2: (m,n) = 1. In this case we must prove that a^m has order n. Let r be the smallest positive integer such that (a^m)^r = 1_G. Since (m,n) = 1, there exists integers s,t such that ms + nt = 1 Therefore,

msr + ntr = r

and

a^r = a^msr · a^ntr

=(a^m)^rs · (aⁿ)^tr

= 1_G.

Therefore, since a has order n, we see that r > n. But since (a^m)ⁿ = 1_G, we have r = n; that is, a^m has order n.

General Case: Suppose that (m,n) = p. Set

m = m₀p,  n = n₀p.

Then (m₀,n₀) = 1, since if (m₀,n₀) > 1, we have (m,n) > p. By case 1, a^p has order n/p = n₀. Therefore, by Case 2, a^m = (a^p)^m₀ has order n₀ = n/(n,m).

Definition 17: Let G be a group, and let H be a subgroup of G. The number of right cosets in H\G is called the index of H in G and is denoted [G:H].

The mapping f:H\G G/H which maps the right coset Ha onto the left coset a^-1H is easily seen to be a bijection, so [G:H] could just as well be defined as the number of left cosets in G/H. From our proof of Lagrange's theorem we see that |G| = |H|·[G:H], in case G is a finite group.

Before leaving this section, it is important to reiterate the notion that the cosets of subgroup H of G form a partition of G. This is of fundamental importance in our studies. To summarize this fact we present the following theorem which is actually just rewording what was already stated. Proof of which is given by Lemma 10 and Lemma 11.

Theorem 18: If H is a subgroup of G and aH and bH are cosets of H then

(1) aH = bH or aH and bH are disjoint.

(2) aH and bH are equivalent sets.